package string;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class RestoreIpAddresses93 {

    @Test
    public void test() {
        System.out.println(restoreIpAddresses("101023"));
        System.out.println(restoreIpAddresses("25525511135"));
        System.out.println(restoreIpAddresses("0000"));
        System.out.println(restoreIpAddresses("000"));
    }

    // first do at 2022.03.06
    public List<String> restoreIpAddresses(String s) {
        char[] ch = s.toCharArray();
        // dotIndexes[i] represents insert dot after ch[i].
        int[] dotIndexes = new int[3];
        List<String> ips = new ArrayList<>();
        insertDotsRecursively(dotIndexes, 0, ch, 0, ips);
        return ips;
    }

    // 不允许: .0X., 允许: .0.
    public void insertDotsRecursively(int[] dotIndexes, int dotCount, char[] ch, int startIndex, List<String> ips) {
        if (dotCount == 3) {
            if (validate(ch, startIndex, ch.length-1)) {
                ips.add(buildIp(ch, dotIndexes));
            }
        } else {
            int remainSegCountAfterInsert = 4 - dotCount - 1;
            if (ch[startIndex] == '0') {
                // .0.
                if (ch.length - (startIndex + 1) >= remainSegCountAfterInsert &&
                        ch.length - (startIndex + 1) <= remainSegCountAfterInsert * 3) {
                    dotIndexes[dotCount] = startIndex;
                    insertDotsRecursively(dotIndexes, dotCount + 1, ch, startIndex + 1, ips);
                }
            } else {
                // .ABC.
                // 注意限制endIndex不要超过数组尾部
                for (int endIndex = startIndex; endIndex < startIndex + 3 && endIndex < ch.length; endIndex++) {
                    if (validate(ch, startIndex, endIndex)) {
                        if (ch.length - (endIndex + 1) >= remainSegCountAfterInsert &&
                                ch.length - (endIndex + 1) <= remainSegCountAfterInsert * 3) {
                            dotIndexes[dotCount] = endIndex;
                            insertDotsRecursively(dotIndexes, dotCount + 1, ch, endIndex + 1, ips);
                        }
                    }
                }
            }
        }
    }

    public String buildIp(char[] ch, int[] dotIndexes) {
        StringBuilder sb = new StringBuilder(ch.length + 3);
        sb.append(ch, 0, dotIndexes[0] + 1);
        sb.append('.');
        sb.append(ch, dotIndexes[0] + 1, dotIndexes[1] - dotIndexes[0]);
        sb.append('.');
        sb.append(ch, dotIndexes[1] + 1, dotIndexes[2] - dotIndexes[1]);
        sb.append('.');
        sb.append(ch, dotIndexes[2] + 1, ch.length - dotIndexes[2] - 1);
        return sb.toString();
    }

    // validate if ch[startIndex, endIndex] is between [0, 255], and not start with '0*'.
    public boolean validate(char[] ch, int startIndex, int endIndex) {
        // 不允许: .0X., 允许: .0.
        if (ch[startIndex] == '0' && startIndex < endIndex) {
            return false;
        }
        if (endIndex - startIndex + 1 > 3) {
            return false;
        }
        int base = 1;
        int n = 0;
        for (int i = endIndex; i >= startIndex; i--) {
            n += (ch[i] - '0') * base;
            base *= 10;
        }
        return n >= 0 && n <= 255;
    }
}
